#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int n = dungeon.size(), m = dungeon[0].size();
    vector<vector<int>> f(n + 1, vector<int>(m + 1, INT_MAX));
    f[n - 1][m] = f[n][m - 1] = 1;
    for (int i = n - 1; i >= 0; i--)
        for (int j = m - 1; j >= 0; j--)
            f[i][j] = max(1, min(f[i + 1][j], f[i][j + 1]) - dungeon[i][j]);
    return f[0][0];
}

int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
    int n = profits.size();
    int cur = 0;
    priority_queue<int> pq;
    vector<pair<int, int>> v;
    for (int i = 0; i < n; i++)
        v.emplace_back(capital[i], profits[i]);
    sort(v.begin(), v.end());

    for (int i = 0; i < k; i++)
    {
        while (cur < n && v[cur].first <= w)
        {
            pq.push(v[cur].second);
            cur++;
        }
        if (pq.size())
        {
            w += pq.top();
            pq.pop();
        }
        else    break;
    }
    return w;
}